//有 n 名工人。 给定两个数组 quality 和 wage ，其中，quality[i] 表示第 i 名工人的工作质量，其最低期望工资为 wage[i] 
//。 
//
// 现在我们想雇佣 k 名工人组成一个工资组。在雇佣 一组 k 名工人时，我们必须按照下述规则向他们支付工资： 
//
// 
// 对工资组中的每名工人，应当按其工作质量与同组其他工人的工作质量的比例来支付工资。 
// 工资组中的每名工人至少应当得到他们的最低期望工资。 
// 
//
// 给定整数 k ，返回 组成满足上述条件的付费群体所需的最小金额 。在实际答案的 10⁻⁵ 以内的答案将被接受。。 
//
// 
//
// 
// 
//
// 示例 1： 
//
// 
//输入： quality = [10,20,5], wage = [70,50,30], k = 2
//输出： 105.00000
//解释： 我们向 0 号工人支付 70，向 2 号工人支付 35。 
//
// 示例 2： 
//
// 
//输入： quality = [3,1,10,10,1], wage = [4,8,2,2,7], k = 3
//输出： 30.66667
//解释： 我们向 0 号工人支付 4，向 2 号和 3 号分别支付 13.33333。 
//
// 
//
// 提示： 
//
// 
// n == quality.length == wage.length 
// 1 <= k <= n <= 10⁴ 
// 1 <= quality[i], wage[i] <= 10⁴ 
// 
//
// Related Topics 贪心 数组 排序 堆（优先队列） 👍 347 👎 0


package LeetCode.editor.cn;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author ldltd
 * @date 2024-05-02 21:15:13
 * @description 857.雇佣 K 名工人的最低成本
 */
public class MinimumCostToHireKWorkers{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 MinimumCostToHireKWorkers fun=new MinimumCostToHireKWorkers();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
		int n=quality.length;
		Integer[] ids=new Integer[n];
		Arrays.setAll(ids,i->i);
		//按照wage/quality排序，存储索引
		Arrays.sort(ids,(a,b)->wage[a]*quality[b]-wage[b]*quality[a]);
		PriorityQueue<Integer> pq=new PriorityQueue<>(k,(a,b)->b-a);
		int sum=0;
		//sum维护k个最小的quality的和
		//ids按照比值从小到大排列，用最大堆存储前k个最小的quality
		for (int i = 0; i <k; i++) {
				pq.offer(quality[ids[i]]);
				sum+=quality[ids[i]];
		}
		//计算前k个最小的quality的和乘以比值最大的wage/quality，即为最小成本
		double res=  sum * ((double)wage[ids[k - 1]]/quality[ids[k-1]]) ;
		//遍历后面的quality，因为比值是递增，后面的一定满足前面的
		for (int i = k; i < n; i++) {
			int q=quality[ids[i]];
			if(q<pq.peek()){
				sum-=pq.poll()-q;
				pq.offer(q);
				res=Math.min(res,sum*((double)wage[ids[i]]/q));
			}
		}
		return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
